#include <iostream>
#include <fstream>
#include <vector>
#include <stdlib.h>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL){}
};

void PrintList(ListNode* head)
{
  if(!head) cout<<"null"<<endl;
  while(head)
  {
    cout << head->val<<" ";
    head = head->next;
  }
  cout <<endl;
}

void DestroyList(ListNode* &head)
{
  if(!head) return;
  ListNode* next;
  while(head)
  {
      next = head->next;
      delete head;
      head = next;
  }

  head = NULL;
}

void PushToList( ListNode* &head, int val)
{
    ListNode *node = new ListNode(val);
    ListNode *tail = NULL;

    if(!head) head = node;
    else
    {
        tail = head;
        while(tail->next) tail = tail->next;

        tail->next = node;
    }
}


void qSortList(ListNode* &start, ListNode* &end)
{
    ListNode *pivot,*prevPivot;
    ListNode *cursor,*preCursor,*temp;

    if(!start) return;
    if(start == end) return;

    pivot  = start;
    prevPivot = NULL;
    preCursor = start;
    cursor = start->next;

    while(cursor)
    {
        temp = cursor->next;
        if(cursor->val < pivot->val)
        {
            if(prevPivot)
            {
                prevPivot->next = cursor;
                cursor->next = pivot;                
            }
            else
            {                
                cursor->next = pivot;
                start = cursor;
            }
            prevPivot = cursor;
            preCursor->next = temp;
        }
        else
        {
            preCursor = cursor;
        }
        cursor = temp;
    }
    end = preCursor;
    
    if(prevPivot)
        qSortList(start,prevPivot);

    qSortList(pivot->next,end);

}


ListNode* mergeSort(ListNode *s1, const ListNode *e1,
                    ListNode *s2, const ListNode *e2, ListNode* &tail)
{
    ListNode* head = NULL;
    ListNode* merged = NULL;

    cout<<s1<<" "<<s2<<" "<<e1<<" "<<e2<<" "<<endl;

    while( ((s1) && (s1!=e1)) &&
           ((s2) && (s2!=e2)) )
    {
        ListNode *p = NULL;

        if( s1->val < s2->val)
        {
            p = s1;
            s1 = s1->next;
        }
        else
        {
            p = s2;
            s2 = s2->next;
        }
        
        if(!head)
        {
            head = p;
            merged = head;
        }
        else
        {
            merged->next = p;
            merged = p;            
        }
    }

    while( (s1) && (s1!=e1) )
    {
        if(!head)
        {
            head = s1;
            merged = head;
        }
        else
        {
            merged->next = s1;
            merged = s1;            
        }
        s1 = s1->next;
    }

    while( (s2) && (s2!= e2) )
    {
        if(!head)
        {
            head = s2;
            merged = head;
        }
        else
        {
            merged->next = s2;
            merged = s2;            
        }
        s2 = s2->next;
    }

    merged->next = NULL;
    tail = merged;

    return head;
}



ListNode* _sortListSolution1(ListNode *head)
{
    int length = 0;
    int width = 0;
    ListNode *lastTail = NULL;
    ListNode *nextHead = NULL;
    int i=0;
    ListNode dummy(0);

    if(!head) return head;
    dummy.next = head;
    

    //get length of list
    nextHead = head;
    while(nextHead){
        length ++;
        nextHead = nextHead->next;
    }
      
    for( width=1; width<length; width+=width)
    {
        nextHead = dummy.next;
        lastTail = &dummy;

        while(nextHead)
        {
            ListNode *thisTail = NULL;
            ListNode *s1,*s2;
            ListNode *e1,*e2;

            cout << nextHead->val <<endl;

            e1 = s1 = nextHead;
            for(i=0; e1 && i<width; i++) e1 = e1->next;

            s2=e2=e1;
            for(i=0; e2 && i<width; i++) e2 = e2->next;
            nextHead = e2;

            lastTail->next = mergeSort(s1,e1,s2,e2,thisTail);
            lastTail = thisTail;
        }
        //cout<<"width "<<width<<": ";
        //PrintList(dummy.next);
    }

    return dummy.next;

}

ListNode* _sortListSolution2(ListNode *head)
{
    ListNode *end;
    qSortList(head,end);
    return head;
}



ListNode* insertSortList(ListNode* head)
{
    ListNode *prevp, *p, *sortp;
    ListNode dummy(0);

    if(!head) return NULL;

    dummy.next = head;

    p = head->next;
    prevp = head;

    while(p)
    {
        sortp = &dummy;
        while( sortp->next != p)
        {
            if(p->val < sortp->next->val)
            {
                prevp->next = p->next;
                p->next = sortp->next;
                sortp->next = p;
                break;
            }
            else
            {
                sortp = sortp->next;
            }
        }

        if(sortp->next == p)
        {
            prevp = p;
            p = p->next;
        }
        else
        {
            p = prevp->next;
        }

    }

    return dummy.next;
}



ListNode* _sortListSolution3(ListNode *head)
{
    return insertSortList(head);
}


ListNode *sortList(ListNode *head)
{
    return _sortListSolution3(head);
}


ListNode* ListConstructor(string line)
{
    const char* p = line.c_str();
    ListNode* head = NULL;
    int integerPos = 0, integerSize = 0;

    while( *p != '\0' )
    {
        while( (*p != '\0') && (*p == ' ') ) {
            integerPos ++;
            p++;
        }

        while( (*p != '\0') && (*p != ' ') )
        {
            integerSize++;
            p++;
        }

        if(integerSize)
        {
            PushToList(head, atoi( line.substr(integerPos,integerSize).c_str() ) );
            integerPos += integerSize;
            integerSize = 0;
        }        
    }

    return head;
}


void ReadTestCase(vector<ListNode*> &testListSet)
{
    string line;
    ifstream testInput("test");
    ListNode* head = NULL;

    if( testInput.is_open() )
    {
        while( getline(testInput,line) )
        {
            head = ListConstructor(line);            
            testListSet.push_back(head);
        }
        testInput.close();        
    }
}


void testMsort(vector<ListNode*> testListSet)
{
    cout<<__FUNCTION__<<endl;

    for( vector<ListNode*>::iterator it = testListSet.begin(); 
         it != testListSet.end(); ++it )
    {
        ListNode *l1 = NULL,*l2 = NULL;
        ListNode *tail = NULL;

        l1 = *it;
        ++it;
        if( it != testListSet.end()) l2 = *it;

        cout<<"Befor:"<<endl;
        cout<<"List 1:"<<endl;
        PrintList(l1);        
        cout<<"List 2:"<<endl;
        PrintList(l2);
        cout<<"After:"<<endl;
        PrintList( mergeSort(l1,NULL,l2,NULL,tail) );
        cout<<"Tail "<<tail->val<<endl;
        cout<<endl;
    }
}


void testQsort(vector<ListNode*> testListSet)
{
    cout<<__FUNCTION__<<endl;
    for( vector<ListNode*>::iterator it = testListSet.begin(); 
         it != testListSet.end(); ++it )
    {
        ListNode* head;

        cout<<"Befor:"<<endl;
        PrintList(*it);

        head = sortList(*it);

        cout<<"After:"<<endl;
        PrintList(head);
        cout<<endl;
    }
}


void testSortList(vector<ListNode*> testListSet)
{
    cout<<__FUNCTION__<<endl;
    for( vector<ListNode*>::iterator it = testListSet.begin(); 
         it != testListSet.end(); ++it )
    {
        ListNode* head;

        cout<<"Befor:"<<endl;
        PrintList(*it);

        head = sortList(*it);

        cout<<"After:"<<endl;
        PrintList(head);
        cout<<endl;
    }
}

int main(int argc, char *argv[])
{
    vector<ListNode*> testListSet;

    ReadTestCase(testListSet);

    //testQsort(testListSet);

    //testMsort(testListSet);

    testSortList(testListSet);
    
}
